import random

LEFT = 1
RIGHT = 2

class RBNode(object):
   """
   A node in a red black tree. See Cormen, Leiserson, Rivest, 
   Stein 2nd edition pg 273.
   """
    
   def __init__(self, Address, NextHop = None, Data = None):
      "Constructor"
      self._address = Address
      self._nexthop = NextHop
      self._data = Data
      self._red = False
      self._left = None
      self._right = None
      self._parent = None
      self._child = []
    
   address = property(fget=lambda self: self._address, doc="The node's Address")
   red = property(fget=lambda self: self._red, doc="Is the node red?")
   left = property(fget=lambda self: self._left, doc="The node's left child")
   right = property(fget=lambda self: self._right, doc="The node's right child")
   parent = property(fget=lambda self: self._parent, doc="The node's parent")
    
   def __str__(self):
      "String representation."
      return str(self.address)
    
   def __repr__(self):
      return str(self)

   def __int__(self):
      return int(self._address)

   def setred(self, Value = False):
      self._red = bool(Value)

   def __getitem__(self, Address):
      retval = None
      if int(Address) == int(self._address):
         retval = self._nexthop

      return retval

   def __contains__(self, Node):
      retval = False
      if isinstance(Node, RBNode):
         if Node.address and self._addr and str(Address) in self._addr:
            retval = True

      return retval

class RBIter(object):
   def __init__(self, tree):
      self.tree = tree
      self.index = -1
      self.node = None
      self.stopped = False

   def __iter__(self):
      return self.node.address

   def next(self):
      if self.stopped or ((self.index + 1) >= len(self.tree)):
         self.stopped = True
         raise StopIteration

      self.index += 1
      if self.index == 0:
         self.node = self.tree.first()
      else:
         self.node = self.tree.next(self.node)

      return self.node


class RBTree(object):
   """
   A red black tree. See Cormen, Leiserson, Rivest, Stein 2nd edition pg 273.
   """
    
   def __init__(self):
      "Construct."
        
      self._nil = RBNode(Address = None)
      "Our nil node, used for all leaves."
        
      self._root = self.nil
      "The root of the tree."

      self.count = 0
        
   root = property(fget=lambda self: self._root, doc="The tree's root node")
   nil = property(fget=lambda self: self._nil, doc="The tree's nil node")

   def __len__(self):
      return self.count

   def __iter__(self):
      return RBIter(self)
    
   def search(self, address, node = None):
      """
      Search the subtree rooted at x (or the root if not given) iteratively
      for the address.  
      
      @return: self.nil if it cannot find it.
      """

      if node is None:
         node = self.root

      while node != self.nil and int(address) != int(node):
         if int(address) < int(node):
            node = node.left
         else:
            node = node.right
            
      return node

   def minimum(self, node = None):
      """
      @return: The minimum value in the subtree rooted at x.
      """
      if node is None:
         node = self.root

      while node.left != self.nil:
         node = node.left

      return node

   def maximum(self, node = None):
      """
      @return: The maximum value in the subtree rooted at x.
      """

      if node is None:
         node = self.root

      while node.right != self.nil:
         node = node.right

      return node
    
   def insert(self, Address, NextHop = None, Data = None):
      znode = RBNode(Address, NextHop, Data)
      "Insert node z into the tree."

      ynode = self.nil
      xnode = self.root
      while xnode != self.nil:
         ynode = xnode
         if int(znode) <= int(xnode):
            xnode = xnode.left
         else:
            xnode = xnode.right

      znode._parent = ynode

      if ynode == self.nil:
         self._root = znode
      elif int(znode) < int(ynode):
         ynode._left = znode
      else:
         ynode._right = znode

      znode._left = self.nil
      znode._right = self.nil
      znode.setred(True)
      self._fixup(znode)
      print znode._left, znode, znode._right, znode.red
      self.count += 1

      return znode
        
   def _fixup(self, znode):
      "Restore red-black properties after insert."
      while znode.parent.red:
         if znode.parent == znode.parent.parent.left:
            ynode = znode.parent.parent.right
            if ynode.red:
               znode.parent.setred(False)
               ynode.setred(False)
               znode.parent.parent.setred(True)
               znode = znode.parent.parent
            else:
               if znode == znode.parent.right:
                  znode = znode.parent
                  self._rotate(znode, LEFT)

               znode.parent.setred(False)
               znode.parent.parent.setred(True)
               self._rotate(znode.parent.parent, RIGHT)
         else:
            ynode = znode.parent.parent.left
            if ynode.red:
               znode.parent.setred(False)
               ynode.setred(False)
               znode.parent.parent.setred(True)
               znode = znode.parent.parent
            else:
               if znode == znode.parent.left:
                  znode = znode.parent
                  self._rotate(znode, RIGHT)

               znode.parent.setred(False)
               znode.parent.parent.setred(True)
               self._rotate(znode.parent.parent, LEFT)

      self.root.setred(False)
    
   def _rotate(self, node, direction):
      if direction == LEFT:
         ynode = node.right
         node._right = ynode.left
         if ynode.left != self.nil:
            ynode.left._parent = node

         ynode._parent = node.parent

         if node.parent == self.nil:
            self._root = ynode
         elif node == node.parent.left:
            node.parent._left = ynode
         else:
            node.parent._right = ynode

         ynode._left = node
         node._parent = ynode
      elif direction == RIGHT:
         xnode = node.left
         node._left = xnode.right
         if xnode.right != self.nil:
            xnode.right._parent = node

         xnode._parent = node.parent
         if node.parent == self.nil:
            self._root = xnode
         elif node == node.parent.right:
            node.parent._right = xnode
         else:
            node.parent._left = xnode

         xnode._right = node
         node._parent = xnode

   def is_rbnode(self, node):
      "@return: num_black"
      # check has _left and _right or neither
      if (node.left and not node.right) or (node.right and not node.left):
          return 0, False

      # check leaves are black
      if not node.left and not node.right and node.red:
          return 0, False

      # if node is red, check children are black
      if node.red and node.left and node.right:
          if node.left.red or node.right.red:
              return 0, False
                    
      # descend tree and check black counts are balanced
      if node.left and node.right:
                
          # check children's parents are correct
          if self.nil != node.left and node != node.left.parent:
              return 0, False
          if self.nil != node.right and node != node.right.parent:
              return 0, False

          # check children are ok
          left_counts, left_ok = self.is_rbnode(node.left)
          if not left_ok:
              return 0, False
          right_counts, right_ok = self.is_rbnode(node.right)
          if not right_ok:
              return 0, False

          # check children's counts are ok
          if left_counts != right_counts:
              return 0, False

          return left_counts, True
      else:
         return 0, True

   def satisfy(self):
      "@return: True iff satisfies all criteria to be red-black tree."

      num_black, is_ok = self.is_rbnode(self.root)
      return is_ok and not self.root._red
